package code;

public class Code204 {
	
	/*
	 * 筛法
	 */
    public int countPrimes(int n) {
        boolean[] vis=new boolean[n+1];
        for(int i=2;i<n;i++){
        	if(!vis[i]){
        		for(int j=2;j*i<n;j++){
        			vis[i*j]=true;
        		}
        	}
        }
        int cnt=0;
        for(int i=2;i<n;i++){
        	if(!vis[i])
        		cnt++;
        }
        return cnt;
    }
    
    public static void main(String[] args){
    	System.out.println(new Code204().countPrimes(10));
    }
}
